//#include <algorithm>  
//#include <iostream>  
//#include <vector>  
//using namespace std;
//struct Road
//{
//    int x;
//    int y;
//    int z;
//};
//bool compare(const Road& p, const Road& q)
//{
//    return p.z < q.z;
//}
//int find(vector<int>& parent, int x)
//{
//    if (x == parent[x]) return x;
//    return parent[x] = find(parent, parent[x]);
//}
//int merge(vector<int>& parent, int x, int y)
//{
//    int rootX = find(parent, x);
//    int rootY = find(parent, y);
//    if (rootX != rootY)
//    {
//        parent[rootY] = rootX;
//        return 1;
//    }
//    return 0;
//}
//int main()
//{
//    int a = 0, b = 0, c = 0;
//    while (cin >> a >> b >> c)
//    {
//        vector<Road> roads(c);
//        vector<int> parent(100);
//        int d = 0, e = 0, f = 0;
//        for (int i = 0; i < 100; i++)
//        {
//            parent[i] = i;
//        }
//        for (int i = 0; i < c; i++)
//            cin >> roads[i].x >> roads[i].y >> roads[i].z;
//        sort(roads.begin(), roads.end(), compare);
//        for (Road& road : roads)
//        {
//            if ((road.x == b || road.y == b) && f < 2)
//            {
//                if (merge(parent, road.x, road.y))
//                {
//                    e += road.z;
//                    d++;
//                    f++;
//                }
//            }
//            else if (road.x != b && road.y != b)
//            {
//                if (merge(parent, road.x, road.y))
//                {
//                    e += road.z;
//                    d++;
//                }
//            }
//            if (d == a - 1)
//                break;
//        }
//        if (d == a - 1 && f <= 2)
//        {
//            cout << e << endl;
//        }
//        else
//        {
//            cout << "-1" << endl;
//        }
//    }
//    return 0;
//}

//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//int main()
//{
//    int n = 0, m = 0, a = 0, x = 0;
//    vector<int> v1;
//    cin >> n >> m;
//    vector<pair<int, int>> v(m);
//    vector<int> v2(n + 1, 0);
//    for (int i = 0; i < m; i++)
//    {
//        cin >> v[i].first >> v[i].second;
//    }
//    for (int i = 0; i < m; i++)
//    {
//        v2[v[i].first]++;
//        if (v[i].second < n)
//        {
//            v2[v[i].second + 1]--;
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        x += v2[i];
//        if (x > a)
//        {
//            a = x;
//            v1.clear();
//            v1.push_back(i);
//        }
//        else if (x == a)
//        {
//            v1.push_back(i);
//        }
//    }
//    for (int i = 0; i < v1.size(); i++)
//    {
//        cout << v1[i];
//        if (i != v1.size() - 1)
//        {
//            cout << " ";
//        }
//    }
//    return 0;
//}